package org.ayachinene.leetcode.problems;

import java.util.Arrays;

public class P4 {

    static class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
            int len2 = nums2.length;

            // 末尾增加哨兵
            nums1 = Arrays.copyOf(nums1, nums1.length + 1);
            nums1[len1] = Integer.MAX_VALUE;
            nums2 = Arrays.copyOf(nums2, nums2.length + 1);
            nums2[len2] = Integer.MAX_VALUE;

            int len = len1 + len2;
            int i1 = 0, i2 = 0;
            int i = 0;
            int cur = 0;
            int pre = 0;
            while (i <= len / 2) {
                if (nums1[i1] <= nums2[i2]) {
                    pre = cur;
                    cur = nums1[i1++];
                } else {
                    pre = cur;
                    cur = nums2[i2++];
                }
                i++;
            }
            if (len % 2 == 0) {
                return (pre + cur) / 2.0;
            }
            return cur;
        }
    }
}
